A Universal Fairness Evaluation Framework for Resource Allocation in Cloud Computing

Abstract

Machine learning is nowadays ubiquitous, providing mechanisms for supporting decision making that leverages big data analytics. However, this recent rise in importance of machine learning also raises societal concerns about the dependability and trustworthiness of systems which depend on such automated predictions. In cloud computing, fairness is one of the most significant indicators to evaluate resource allocation algorithms, which reveals whether each user is allocated as much as that of all other users having the same bottleneck. However, how fair an allocation algorithm is remains an urgent issue. In this paper, we propose Dynamic Evaluation Framework for Fairness (DEFF), a framework to evaluate the fairness of an resource allocation algorithm. In our framework, two sub-models, Dynamic Demand Model (DDM) and Dynamic Node Model (DNM), are proposed to describe the dynamic characteristics of resource demand and the computing node number under cloud computing environment. Combining Fairness on Dominant Shares and the two sub-models above, we finally obtain DEFF. In our experiment, we adopt several typical resource allocation algorithms to prove the effectiveness on fairness evaluation by using the DEFF framework..

Introduction

I. INTRODUCTION

In cloud computing, computational resources are highly integrated in the “cloud”. Services and applications are provided by virtual machines running over the cloud platform. Hence, computational resources, such as CPU, RAM, bandwidth etc., should be properly scheduled for better service provision. Resource allocation algorithm is widely studied in recent works on shared communication and computing systems. max-min fairness[4][6] ensures the allocations of the users with minimal resource demands. In proportional fairness[10][14], it attempts to find a balance point in resource allocation among the competing interests. Α fairness attempts to determine an equilibrium point between allocation fairness and the utilization efficiency of resources. Ref.[17] presents a game theory based approach which introduces a tradeoff between relay fairness and system throughput.

In multi-type resource allocation, ref.[1][3] and ref.[5][11][13] focus on multiple instances of the same resource. Ref.[7] proposes Dominant Resource Fairness (DRF) which is designed to ensure the fairness in the allocation of multiple types of resources, such as CPU, RAM and bandwidth etc. [2][8] propose genetic algorithm based approaches to obtain the optimal allocation.

Machine Learning (ML) is nowadays ubiquitous, as most organizations take advantage of it to perform or support decisions within their systems [1], [2]. ML is an area of Artificial Intelligence (AI) in which we use a set of statistical methods and computational algorithms to allow computers to learn from data [3]. ML algorithms can be divided into two main groups: supervised and unsupervised. Supervised learning involves the development of computational models for estimating an output based on previously known inputs and outputs. In unsupervised learning, the models are built based solely on existing inputs but there are no associated outputs that may be used for sake of training.

We may face fairness and transparency issues for both groups of algorithms. It is now commonplace to run ML systems in cloud-based infrastructures, motivated by issues such as elasticity, robustness, and ease of operation [4]. In practice, cloud services are fueling big data analytics, allowing organizations to make better and faster decisions using data that previously were hard or impossible to use [5]. This raises many opportunities in today’s competitive environment, by offering many services using highly scalable technologies on a pay-as-you-go basis. However, it also creates new challenges regarding trust, a paramount concern in critical systems [5]. Regulatory institutions have long focused these properties namely in OECD’s fair information practices [6] and in EU Privacy Directive 95/46/EC [7]. However, such legislation has never received as much emphasis as now. The new EU General Data Protection Regulation (GDPR) [8] shifts the onus to the organizations, demanding them to demonstrate that they are taking the appropriate measures to protect the legal rights of the individuals and their data, requiring privacy-preserving, fair and transparent systems.

V. FUTURE WORK

Future extensions of this work will consider an additional pricing scheme: differentiated pricing, in which the operator can choose a per-job price for each client independent of the client’s resource requirements. We do not consider such a pricing plan here since bundled and resource pricing are more practically relevant; in practice clients are generally not charged different per-job prices. One could also extend our work to take into account job completion deadlines, which impose an additional constraint on the resources allocated at any given time. We also plan to consider tradeoffs between revenue, fairness, and operational efficiency, e.g., through examining the total amount of leftover resources.

Conclusion

In this work, a framework for evaluating two cloud pricing strategies–bundled and resource pricing–in terms of their resulting fairness and revenue. We first characterize client demand for resources as a function of the prices offered under these different pricing plans. After showing some analytical bounds on the tradeoff between fairness and revenue, we compare achieved fairness and revenue under the two pricing plans. We finally use data taken from a Google cluster to numerically evaluate the impact of resource capacity and volume discounts on the operator’s fairness-revenue tradeoff. This paper proposes DEFF, a framework for dynamic evaluation of fairness based on dominant share. Aiming to the dynamic resource demand and computing node in cloud computfigure ing, we introduce time and probability factor to establish two sub-models: 1) Dynamic Demand Model (DDM) and 2) Dynamic Node Model (DNM). By combining these two model, we establish Dynamic Evaluation Framework for Fairness (DEFF) to give a measurement to resource allocation algorithms. To evaluate the effectiveness of DEFF, we adopt two typical allocation algorithms, DRF and max-min, and a utility-based fairness algorithm, ?-fairness in our experiment. According to experiment results, DEFF shows preferably effectiveness under dynamic demand and node number. Our framework provides significant reference for determining resource allocation algorithms in cloud computing.

References

[1] BARUAH S K, GEHRKE J, PLAXTON C G. Fast scheduling of periodic tasks on multiple resources[ C]. IPPS. IEEE Computer Society, 1995,280-288. [2] CAMPEGIANI P. A Genetic Algorithm to Solve the Virtual Machines Resources Allocation Problem in Multi-tier Distributed Systems[C]. VPACT’09, 2009. [3] BARUAH S K, COHEN N K, PLAXTON C G, and Donald A. Varvel. Proportionate Progress: A Notion of Fairness in Resource Allocation[J]. Algorithmica, 1996, 15(6): 600–625. [4] BERTSEKAS D, GALLAGER R. Data Networks[M]. Prentice Hall, 1992. [5] BLANQUER J M, ÖZDEN B. Fair Queuing for Aggregated Multiple Links[C]. SIGCOMM, 2001: 189–197. [6] CHARNY A, CLARK D, JAIN R. Congestion Control with Explicit Rate Indication[C]. International Conference on Communications, 1995(3): 1954-1963. [7] GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant Resource Fairness: Fair Allocation of Multiple Resource Types[J]. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, 2011, 24–24. [8] GU J H, HU J H, ZHAO T H, et al. A New Resource Scheduling Strategy Based on Genetic Algorithm in Cloud Computing Environment[J]. Journal of Computers, 2012(7): 42–52. [9] WONG C J, SEN S, LAN T, et al. Multi-resource Allocation: Fairness-Efficiency Tradeoffs in A Unifying Framework[C]. In INFOCOM, IEEE, 2012: 1206–1214. [10] KELLY F P. Charging and Rate Control for Elastic Traffic[J]. European Transaction on Telecommunications, 1997(8): 33-37. [11] KLEINBERG J M, RABANI Y, and TARDOS É. Fairness in Routing and Load Balancing[J]. Journal of Computer System Sciences, 2001, 63(1):2–20. [12] LAN T, KAO D, CHIANG M, et al. An Axiomatic Theory of Fairness in Network Resource Allocation[ C]. In INFOCOM, IEEE, 2010, 1343–1351. [13] LIU Y and KNIGHTLY E W. Opportunistic Fair Scheduling over Multiple Wireless Channels[C]. INFOCOM, 2003. [14] MASSOULIÉ L and ROBERTS J. Bandwidth Sharing: Objectives and Algorithms[C]. INFOCOM, 1999, 1395–1403. [15] TAN L, PUGH A C and YIN M. Rate-based Congestion Control in ATM Switching Networks Using A Recursive Digital Filter[J]. Control Engineering Practice, 2003, 11(10): 1171–1181. [16] TIAN J F, YUAN P, and LU Y Z. Security for Resource Allocation Based on Trust and Reputation in Computational Economy Model for Grid[C]. Frontier of Computer Science and Technology 2009, IEEE, 2009: 339–345. [17] TENG Y L, HUANG T, LIU Y Y, et al. Cooperative Game Approach for Scheduling in Two-Virtual- Antenna Cellular Networks with Relay Stations Fairness Consideration[J]. China Communications, 2013, 10(2):56–70. [18] ZHU D, MOSSÉ D, and MELHEM R G. Multiple- Resource Periodic Scheduling Problem: How Much Fairness is Necessary?[C] RTSS, IEEE Computer Society, 2003: 142–151. [19] ZUKERMAN M, TAN L S, WANG H W, et al. Efficiency- Fairness Tradeoff in Telecommunications Networks[C]. IEEE Communications Letters, 2005: 643–645.

Copyright

Copyright © 2023 Prof. Pragati Patil , Chandrashekhar G. Bhagat . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.